package labuladong;

/**
 * 给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性，其中第i个
 * 物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少
 */

public class _01背包 {
    public static void main(String[] args) {
        // 答案6
        int N = 3, W = 4;
        int[] wt = {2, 1, 3};
        int[] val = {4, 2, 3};
        int target = oneZeroBag(N, W, wt, val);
        System.out.println(target);
    }

    public static int oneZeroBag(int N, int W, int[] wt, int[] val) {
        // dp[i][w]定义表示对于前i个物品，当前背包的容量为w， 这种情况下可以装的最大价值是dp[i][w]
        // 定义dp数组
        int[][] dp = new int[N + 1][W + 1];
        // 将第一行和第一列全部置0(因为没有物品或者背包没有空间的时候，能装的最大价值是0)
        for (int i = 0 ; i <= N ; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0 ; i <= W ; i++) {
            dp[0][i] = 0;
        }

        // 遍历所有状态
        for (int i = 1 ; i <= N ; i++) {
            for (int j = 1 ; j <= W ; j++) {
                // 由于i是从0开始的，i-1表示第i件物品的属性
                // 背包容量不够，这种情况下只能选择不装入背包
                if (j - wt[i - 1] < 0) {
                    // 继承上一行的结果
                    dp[i][j] = dp[i - 1][j];
                }else {
                    // 如果装了第i件商品，就要寻求剩余重量w-wt[i-1]限制下的最大价值，加上第i个物品的价值val[i-1]
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[N][W];
    }
}
